#pragma once
#include<bitset>



namespace Bloom {
	template<class T>
	struct BKDRHashFunc
	{
		//BKDR
		size_t operator()(const T& s)
		{
			int Hashi = 0;
			for (auto e : s)
			{
				Hashi *= 131;
				Hashi += e;
			}
			return Hashi;
		}
	};
	template<class T>
	struct APHashFunc
	{
		//AP
		size_t operator()(const T& s)
		{
			size_t hash = 0;
			int i = 0;
			for (auto str : s)
			{
				if ((i & 1) == 0)
				{
					hash ^= ((hash << 7) ^ str ^ (hash >> 3));
				}
				else
				{
					hash ^= (~((hash << 11) ^ str ^ (hash >> 5)));
				}
				i++;
			}
			return hash;
		}
	};
	template<class T>
	struct DJBKHashFunc
	{
		//AP
		size_t operator()(const T& s)
		{
			register size_t hash = 5381;
			for(auto str:s)
			{
				hash += (hash << 5) + str;
			}
			return hash;
		}
	};
	// 假设N是最多存储的数据个数
	// 平均存储一个值，开辟X个位
	template<
	size_t N,
	size_t X = 6,
	class K= string,
	class HashFunc1 = BKDRHashFunc<K>,
	class HashFunc2 = APHashFunc<K>,
	class HashFunc3 = DJBKHashFunc<K>>
	class BloomFilter {
	public:
		void set(const K& key)
		{
			size_t hashi1 = HashFunc1()(key) % (N * X);
			size_t hashi2 = HashFunc2()(key) % (N * X);
			size_t hashi3 = HashFunc3()(key) % (N * X);
			_bt.set(hashi1);
			_bt.set(hashi2);
			_bt.set(hashi3);
		}
		bool test(const K& key)
		{
			size_t hashi1 = HashFunc1()(key) % (N * X);
			if (!_bt.test(hashi1))
			{
				return false;
			}
			size_t hashi2 = HashFunc2()(key) % (N * X);
			if (!_bt.test(hashi2))
			{
				return false;
			}
			size_t hashi3 = HashFunc3()(key) % (N * X);
			if (!_bt.test(hashi3))
			{
				return false;
			}
			//不在是准确的
			return true; //在不一定是准确得
		}
	private:
		//这里的空间一定要开足够
		std::bitset<N*X> _bt;
	};

	void testBloom()
	{
		BloomFilter<10> bf;
		string str[] = { "猪八戒","孙悟空","唐三藏","白龙马","等等等" };
		for (auto& s : str)
		{
			bf.set(s);
		}
		for (auto& s : str)
		{
			cout << bf.test(s) << endl;;
		}
	}



}


